// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2002-2003 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: string_index.cc,v 1.25 2010-03-11 15:16:42 carzanig Exp $
//
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <cassert>

#include "siena/forwarding.h"
#include "siena/allocator.h"

#include "fwd_table.h"
#include "string_index.h"
#include "statistics.h"

namespace siena {

static const int EndChar = -1;

static const mask_t EQ_Mask = 1;
static const mask_t SF_Mask = 2;
static const mask_t LT_Mask = 4;
static const mask_t GT_Mask = 8;
static const mask_t NE_Mask = 16;
static const mask_t PF_Mask = 32;
static const mask_t SS_Mask = 64;

static const mask_t Complete_Mask = EQ_Mask | SF_Mask | LT_Mask | GT_Mask | NE_Mask;

void StringIndex::consolidate(FTAllocator &) throw() {
}

//
// this algorithm is taken more or less directly from R. Sedgewick's
// "Algorithms in C" 3rd Ed. pp 638--639.  The only difference is the
// addition of my subtree mask.
//
PTSTNode * StringIndex::insert_complete(const char * s, const char * end, 
					FTAllocator & ftmemory,
					const mask_t mask) throw() {
    PTSTNode * pp = 0;
    PTSTNode ** p = &root;
    while (*p != 0) {
	pp = *p;
	pp->mask |= mask;
	if (s == end) {
	    if (pp->c == EndChar) return pp;
            p = &(pp->left);
	} else if (*s == pp->c) {
	    ++s;
            p = &(pp->middle);
        } else if (*s < pp->c) {
            p = &(pp->left);
	} else {
            p = &(pp->right);
	}
    }

    for (;;) {
	if (s == end) 
	    return *p = new (ftmemory)PTSTNode(EndChar, pp, mask);
	*p = new (ftmemory)PTSTNode(*s, pp, mask);
	pp = *p;
	++s;
        p = &(pp->middle);
    }
}

PTSTNode * StringIndex::insert_partial(const char * s, const char * end,
				       FTAllocator & ftmemory,
				       const mask_t mask) throw() {
    // precondition s != end
    PTSTNode * pp = 0;
    PTSTNode ** p = &root;
    while (*p != 0) {
	pp = *p;
	pp->mask |= mask;
	if (*s == pp->c) {
	    if (++s == end) return pp;
            p = &(pp->middle);
        } else if (*s < pp->c) {
            p = &(pp->left);
	} else {
            p = &(pp->right);
	}
    }
    for (;;) {
	*p = new (ftmemory)PTSTNode(*s, pp, mask);
	pp = *p;
        if (++s == end) return pp;
        p = &(pp->middle);
    }
}

static PTSTNode * backtrack_next(register PTSTNode * p, 
				 register const mask_t mask) throw() {
    register PTSTNode * pp;
    while ((pp = p->up) != 0) {
	if (p == pp->left) goto back_from_left;
	if (p == pp->middle) goto back_from_middle;
	if (p == pp->right) goto back_from_right;

	assert(false);		// this should NEVER happen!

    back_from_left:
	if ((pp->middle) && (pp->middle->mask & mask)) 
	    return pp->middle;
    back_from_middle:
	if ((pp->right) && (pp->right->mask & mask)) 
	    return pp->right;
    back_from_right:
	p = pp;
    }
    return 0;
}
//
// returns the node corresponding to the next complete string that is
// lexicographically greater than the (complete) string represented by
// the given node p
//
static PTSTNode * next(register PTSTNode * p, 
		       register const mask_t mask) throw() {
    if ((p->left) && (p->left->mask & mask)) {
	p = p->left;
    } else if ((p->middle) && (p->middle->mask & mask)) {
	p = p->middle;
    } else if ((p->right) && (p->right->mask & mask)) {
	p = p->right;
    } else {
	if ((p = backtrack_next(p, mask)) == 0)
	    return 0;
    }
    for (;;) {
	if ((p->left) && (p->left->mask & mask)) {
	    p = p->left;
        } else if (p->c == EndChar) {
	    return p; 
	} else if ((p->middle) && (p->middle->mask & mask)) {
            p = p->middle;
	} else if ((p->right) && (p->right->mask & mask)) {
	    p = p->right;
	} else {
	    assert(false);	// this should NEVER happen!
	}
    }
}

static PTSTNode * prev(register PTSTNode * p,
		       register const mask_t mask) throw() {
    // first we backtrack
    register PTSTNode * pp = p;
    while ((p = p->up)) {
	if (pp == p->left) goto back_from_left;
	if (pp == p->middle) goto back_from_middle;
	if (pp == p->right) goto back_from_right;
	assert(false);

    back_from_right:
	if (p->c == EndChar) return p;
	if ((p->middle) && (p->middle->mask & mask)) {
	    p = p->middle;
	    break;
	}
    back_from_middle:
	if ((p->left) && (p->left->mask & mask)) {
	    p = p->left;
	    break;
	}
    back_from_left:
	pp = p;
    }
    if (p == 0) 
	return 0;
    // then we move forward keeping to the rightmost path
    for(;;) {
	if ((p->right) && (p->right->mask & mask)) {
	    p = p->right;
	} else if ((p->middle) && (p->middle->mask & mask)) {
	    p = p->middle;
	} else if (p->c == EndChar) {
	    return p; 
	} else if ((p->left) && (p->left->mask & mask)) {
	    p = p->left;
	} else {
	    assert(false);	// this should NEVER happen!
	}
    }
}

static inline const PTSTNode * last(register const PTSTNode * pp,
				    register const mask_t mask) throw() {
    if (pp == 0 || (pp->mask & mask) == 0) return 0;
    for (;;) {
	if ((pp->right) && (pp->right->mask & mask)) {
	    pp = pp->right;
	} else if ((pp->middle) && (pp->middle->mask & mask)) {
            pp = pp->middle;
	} else if (pp->c == EndChar) {
	    return pp;
	} else if ((pp->left) && (pp->left->mask & mask)) {
	    pp = pp->left;
	} else {
	    assert(false);	// this should NEVER happen!
	}
    }
}

static inline const PTSTNode * upper_bound(register const PTSTNode * p,
					   register const char * begin,
					   register const char * end,
					   register const mask_t mask) throw() {
    //
    // precondition root != 0
    //
    if ((p->mask & mask) == 0) return 0;
    register const PTSTNode * ub;
    if (begin == end) {
	ub = p;
    } else {
	register char s = *begin;
	ub = 0;
	for (;;) {
	    if (s == p->c) {
		if ((p->right) && (p->right->mask & mask))
		    ub = p->right;

		if ((p->middle) && (p->middle->mask & mask)) {
		    p = p->middle;
		    if (++begin == end) {
			if (p->c == EndChar) {
			    if ((p->right) && (p->right->mask & mask)) {
				ub = p->right;
			    } 
			} else {
			    ub = p;
			}
			break;
		    } 
		    s = *begin;
		} else {
		    break;
		}
	    } else if (s < p->c) {
		if ((p->middle) && (p->middle->mask & mask)) {
		    ub = p->middle;
		} else if ((p->right) && (p->right->mask & mask)) {
		    ub = p->right;
		}
		if ((p->left) && (p->left->mask & mask)) {
		    p = p->left;
		} else {
		    break;
		}
	    } else { 		// (s > pp->c)
		if ((p->right) && (p->right->mask & mask)) {
		    p = p->right;
		} else {
		    break;
		}
	    }
	}
	if (ub == 0) return 0;
    }
    while (ub->c != EndChar) {
	if ((ub->left) && (ub->left->mask & mask)) {
	    ub = ub->left;
	} else if ((ub->middle) && (ub->middle->mask & mask)) {
	    ub = ub->middle;
	} else if ((ub->right) && (ub->right->mask & mask)) {
	    ub = ub->right;
	} else {
	    assert(false);	// this should NEVER happen!
	}
    }
    return ub;
}

void insert_between(SICompleteDescr * d, PTSTNode * p, PTSTNode * n) throw() {
    if (p == 0) {
	d->next_gt = 0;
    } else {
	SICompleteDescr * pd;
	pd = static_cast<SICompleteDescr*>(p->data);
	d->next_gt = (pd->gt || pd->ne) ? pd : pd->next_gt;
	if (d->lt != 0 || d->ne != 0) {
	    for (;;) {
		pd->next_lt = d;
		if (pd->lt != 0 || pd->ne != 0) break;
		p = prev(p, Complete_Mask);
		if (p == 0) break;
		pd = static_cast<SICompleteDescr*>(p->data);
	    }
	}
    }

    if (n == 0) {
	d->next_lt = 0;
    } else {
	SICompleteDescr * nd;
	nd = static_cast<SICompleteDescr*>(n->data);
	d->next_lt = (nd->lt || nd->ne) ? nd : nd->next_lt;
	if (d->gt != 0 || d->ne != 0) {
	    for (;;) {
		nd->next_gt = d;
		if (nd->gt != 0 || nd->ne != 0) break;
		n = next(n, Complete_Mask);
		if (n == 0) break;
		nd = static_cast<SICompleteDescr*>(n->data);
	    }
	}
    }
}

ConstraintType * StringIndex::add_eq(const string_t & v,
				 FTAllocator & ftmemory) throw() { 
    PTSTNode * np = insert_complete(v.begin, v.end, ftmemory, EQ_Mask);
    SICompleteDescr * d;
    if (np->data == 0) {
	d = new (ftmemory)SICompleteDescr();
	np->data = d;
	d->eq = new (ftmemory)ConstraintType();
	d->ne = 0;
	d->lt = 0;
	d->gt = 0;
	d->sf = 0;
	insert_between(d, prev(np, Complete_Mask), next(np, Complete_Mask));
	return d->eq;
    }
    d = static_cast<SICompleteDescr*>(np->data);
    if (d->eq == 0) {
	d->eq = new (ftmemory)ConstraintType();
    }
    return d->eq;
}

ConstraintType * StringIndex::add_sf(const string_t & v,
				 FTAllocator & ftmemory) throw() { 
    PTSTNode * np = insert_complete(v.begin, v.end, ftmemory, SF_Mask);
    SICompleteDescr * d;
    if (np->data == 0) {
	d = new (ftmemory)SICompleteDescr();
	np->data = d;
	d->eq = 0;
	d->ne = 0;
	d->lt = 0;
	d->gt = 0;
	d->sf = new (ftmemory)ConstraintType();
	insert_between(d, prev(np, Complete_Mask), next(np, Complete_Mask));
	return d->sf;
    }
    d = static_cast<SICompleteDescr*>(np->data);
    if (d->sf == 0) {
	d->sf = new (ftmemory)ConstraintType();
    }
    return d->sf;
}

ConstraintType * StringIndex::add_ne(const string_t & v,
				 FTAllocator & ftmemory) throw() { 
    PTSTNode * np = insert_complete(v.begin, v.end, ftmemory, NE_Mask);
    SICompleteDescr * d;
    if (np->data == 0) {
	d = new (ftmemory)SICompleteDescr();
	np->data = d;
	d->eq = 0;
	d->ne = new (ftmemory)ConstraintType();
	d->lt = 0;
	d->gt = 0;
	d->sf = 0;
	insert_between(d, prev(np, Complete_Mask), next(np, Complete_Mask));
	return 	d->ne;
    }
    d = static_cast<SICompleteDescr*>(np->data);
    if (d->ne == 0) {
	d->ne = new (ftmemory)ConstraintType();
	insert_between(d, prev(np, Complete_Mask), next(np, Complete_Mask));
    }
    return d->ne;
}

ConstraintType * StringIndex::add_lt(const string_t & v,
				 FTAllocator & ftmemory) throw() { 
    PTSTNode * np = insert_complete(v.begin, v.end, ftmemory, LT_Mask);
    SICompleteDescr * d;
    if (np->data == 0) {
	d = new (ftmemory)SICompleteDescr();
	np->data = d;
	d->eq = 0;
	d->ne = 0;
	d->lt = new (ftmemory)ConstraintType();
	d->gt = 0;
	d->sf = 0;
	insert_between(d, prev(np, Complete_Mask), next(np, Complete_Mask));
	return 	d->lt;
    }
    d = static_cast<SICompleteDescr*>(np->data);
    if (d->lt == 0) {
	d->lt = new (ftmemory)ConstraintType();
	insert_between(d, prev(np, Complete_Mask), next(np, Complete_Mask));
    }
    return d->lt;
}

ConstraintType * StringIndex::add_gt(const string_t & v,
				 FTAllocator & ftmemory) throw() { 
    PTSTNode * np = insert_complete(v.begin, v.end, ftmemory, GT_Mask);
    SICompleteDescr * d;
    if (np->data == 0) {
	d = new (ftmemory)SICompleteDescr();
	np->data = d;
	d->eq = 0;
	d->ne = 0;
	d->lt = 0;
	d->gt = new (ftmemory)ConstraintType();
	d->sf = 0;
	insert_between(d, prev(np, Complete_Mask), next(np, Complete_Mask));
	return 	d->gt;
    }
    d = static_cast<SICompleteDescr*>(np->data);
    if (d->gt == 0) {
	d->gt = new (ftmemory)ConstraintType();
	insert_between(d, prev(np, Complete_Mask), next(np, Complete_Mask));
    }
    return d->gt;
}

ConstraintType * StringIndex::add_pf(const string_t & v,
				 FTAllocator & ftmemory) throw() { 
    PTSTNode * np = insert_partial(v.begin, v.end, ftmemory, PF_Mask);
    SIPartialDescr * d;
    if (np->data == 0) {
	d = new (ftmemory)SIPartialDescr();
	np->data = d;
	d->ss = 0;
	d->pf = new (ftmemory)ConstraintType();
	return d->pf;
    }
    d = static_cast<SIPartialDescr*>(np->data);
    if (d->pf == 0) {
	d->pf = new (ftmemory)ConstraintType();
    }
    return d->pf;
}

ConstraintType * StringIndex::add_ss(const string_t & v,
				 FTAllocator & ftmemory) throw() { 
    PTSTNode * np = insert_partial(v.begin, v.end, ftmemory, SS_Mask);
    SIPartialDescr * d;
    if (np->data == 0) {
	d = new (ftmemory)SIPartialDescr();
	np->data = d;
	d->pf = 0;
	d->ss = new (ftmemory)ConstraintType();
	return d->ss;
    }
    d = static_cast<SIPartialDescr*>(np->data);
    if (d->ss == 0) {
	d->ss = new (ftmemory)ConstraintType();
    }
    return d->ss;
}

ConstraintType * StringIndex::add_re(const string_t & v,
				 FTAllocator & ftmemory) throw(bad_constraint) {
    throw new bad_constraint ("regular expressions not supported yet");
}

ConstraintType * StringIndex::add_any(FTAllocator & ftmemory) throw() {
    if (any_value == 0)
	any_value = new (ftmemory)ConstraintType();
    return any_value;
}

//
// This class implements a set with a probabilistically fast
// insertion/membership method.  We use it in the match function to
// keep track of the substring constraints that we have already
// matched, and therefore that we should simply skip.  The primary
// design goals here are to obtain speed in the most common case using
// a self-contained, static structure.
//
// Implementation note: the set is simply represented by an array.
// The membership is first checked using a simple Bloom set.  If the
// membership check given by the Bloom set is negative, then we know
// the element does not exist and we simply add it to the array (and
// return TRUE).  This should be by far the most frequent execution
// path.  In case the membership test returns true, then we don't
// actually know whether this constraint has been already processed,
// or the hash of this constraint collides with that of a previously
// matched but unrelated constraint.  In this case, we do an
// inefficient linear search.
//
// Note also that the array has a fixed length, so in some cases, this
// data structure will return the wrong answer.  In these cases, we
// are conservative, meaning that we assume that this is a new
// constraint.  This might cause the forwarding algorithm to match
// filters that do not actually match.
//
// In summary, I think this is a perfectly fine data structure that
// does its job nicely, we might however reconsider this design at
// some point.
//
class b_set_constrp {
private:
    typedef unsigned long long bitvector_t;
    static const unsigned int size = sizeof(bitvector_t) * 8;
    static const unsigned int vsize = 256;

    bitvector_t bv;
    unsigned int vpos;
    const ConstraintType * values[vsize];

    static unsigned long compute_hash(const ConstraintType * x) {
	//
	// this function uses the multiplicative hash method described
	// in CLRS 2nd Ed. pp 231--232
	//
	static const unsigned long p = 10; // M==1024
	static const unsigned long w = 32; // 12 bits is hash value is plenty
	static const unsigned long s = 2654435769UL;

 	register unsigned long k = reinterpret_cast<unsigned long>(x);

	return (k * s) >> (w - p); 
    }

public:
    b_set_constrp() throw () : bv(0), vpos(0) { }

    bool insert(const ConstraintType * x) throw () {
	bitvector_t m = 1;
	unsigned pos = compute_hash(x);
	m <<= (pos % size);
	if (bv & m) {
	    for(unsigned int i = 0; i < vpos; ++i)
		if (values[i] == x) return false;
	    return true;
	} else {
	    bv |= m;
	    if (vpos < vsize)
		values[vpos++] = x;
	    return true;
	}
    }
};

bool StringIndex::match(const string_t & v, CProcessor & cp) const throw() { 
#ifdef WITH_STATISTICS
    sff_timer_stack.push(string_match_timer);
#endif
    if ((any_value) && 		// first we try the any-value constraint
	cp.process_constraint(any_value)) {
#ifdef WITH_STATISTICS
	sff_timer_stack.pop();
#endif
	return true;
    }

    bool result = tst_match (v, cp);
#ifdef WITH_STATISTICS
    sff_timer_stack.pop();
#endif
    return result;
}

bool StringIndex::tst_match(const string_t & v, CProcessor & cp) const throw() {
    register const PTSTNode * p = root;
    if (p == 0) return false;

    register const char * sp = v.begin;
    register char s = *sp;
    
#ifdef WITH_STATISTICS    
    string_matcher_bytes += v.end - v.begin;
#endif

    b_set_constrp ss_cset;
				// in this first pass, we look for all
    while ((p)) {		// constraints: suffix, prefix,
	if (s < p->c) {		// substring and complete constraints
	    p = p->left;
	} else if (s == p->c) {
	    if (p->c != EndChar) {
		if (p->data != 0) { // here we have a partial match
		    SIPartialDescr * d = static_cast<SIPartialDescr*>(p->data);
		    if ((d->pf) && cp.process_constraint(d->pf))
			return true;
		    if ((d->ss) && ss_cset.insert(d->ss)
			&& cp.process_constraint(d->ss))
			return true;
		}
		p = p->middle;
		++sp;
		s = (sp == v.end) ? EndChar : *sp;
	    } else {
		// here we have a complete match
		// it should always be np->data != 0
		SICompleteDescr * d = static_cast<SICompleteDescr*>(p->data);
		if (d->eq != 0 && cp.process_constraint(d->eq))
		    return true;
		if (d->sf != 0 && cp.process_constraint(d->sf))
		    return true;
		SICompleteDescr * curs;
		for(curs = d->next_lt; curs != 0; curs = curs->next_lt) {
		    if ((curs->lt) && cp.process_constraint(curs->lt))
			return true;
		    if ((curs->ne) && cp.process_constraint(curs->ne))
			return true;
		}
		for(curs = d->next_gt; curs != 0; curs = curs->next_gt) {
		    if ((curs->gt) && cp.process_constraint(curs->gt)) 
			return true;
		    if ((curs->ne) && cp.process_constraint(curs->ne))
			return true;
		}
		goto match_sf_ss;
	    }
        } else {  		// p->c > s
            p = p->right;
	}
    }
    // np is now a middle node that represents the longest
    // (incomplete) prefix of the target
    if ((p = upper_bound(root, v.begin, v.end, Complete_Mask))) {
	SICompleteDescr * d = static_cast<SICompleteDescr*>(p->data);
	do {
	    if ((d->lt) && cp.process_constraint(d->lt))
		return true;
	    if ((d->ne) && cp.process_constraint(d->ne))
		return true;
	} while((d = d->next_lt));
	d = static_cast<SICompleteDescr*>(p->data);
	while((d = d->next_gt)) {
	    if ((d->gt) && cp.process_constraint(d->gt))
		return true;
	    if ((d->ne) && cp.process_constraint(d->ne))
		return true;
	}
    } else if ((p = last(root, GT_Mask | NE_Mask))) {
	SICompleteDescr * d = static_cast<SICompleteDescr*>(p->data);
	do {
	    if ((d->gt) && cp.process_constraint(d->gt))
		return true;
	    if ((d->ne) && cp.process_constraint(d->ne))
		return true;
	} while((d = d->next_gt));
    }

 match_sf_ss:
    const char * spl = v.begin;
    if (spl == v.end) return false; // this takes care of empty strings
    while(++spl != v.end) {
	sp = spl;
	s = *sp;
	p = root;
	while ((p) && (p->mask & (SS_Mask | SF_Mask))) { 
	    if (s < p->c) {
		p = p->left;
	    } else if (s == p->c) {
		if (p->c != EndChar) {
		    if (p->data != 0) { // here we have a partial match
			SIPartialDescr * d = static_cast<SIPartialDescr*>(p->data);
			if (d->ss != 0 && ss_cset.insert(d->ss)
			    && cp.process_constraint(d->ss))
			    return true;
		    }
		    p = p->middle;
		    ++sp;
		    s = (sp == v.end) ? EndChar : *sp;
		} else {
		    // here we have a complete match
		    // it should always be np->data != 0
		    SICompleteDescr * d = static_cast<SICompleteDescr*>(p->data);
		    if (d->sf != 0 && cp.process_constraint(d->sf))
			return true;
		    break;
		}
	    } else {  		// p->c > s
		p = p->right;
	    }
	}
    }
    return false;
}

} // end namespace siena
